package Algorithm.string;

/**
 * @Desc:   取出最长前缀
 * @author: cww
 * @DateTime: 2020-03-29 10:14
 */

public class LongestCommonPrefix {
    public static void main(String[] args) {
        String[] strs = new String[]{"flower","flow","flight"};
        System.out.println(longestCommonPrefix3(strs));

    }

    /**
     * 水平扫描法
     * @param strs
     * @return
     */
    public static String longestCommonPrefix(String[] strs){
        if (strs == null || strs.length == 0) return "";
        String prev = strs[0];
        for (int i = 1; i < strs.length; i++) {
            while (strs[i].indexOf(prev) != 0) {
                prev = prev.substring(0, prev.length() -1);
                if (prev.isEmpty()) return "";
            }
        }
        return prev;
    }

    /**
     * 水平扫描法
     * 用数组第一个字符串每一位与数组其他位置字符串对应位置进行比对，
     * @param strs
     * @return
     */
    public static String longestCommonPrefix2(String[] strs){
        if (strs == null || strs.length ==0) return "";
        // 遍历数组中首个字符的每一列，再用这一列去比对数组中每一个字符串对应列
        for(int i=0;i<strs[0].length();i++){
            // 拿到当前字符串的列
            char c = strs[0].charAt(i);
            // 遍历数组首位之后的所有字符串
            for(int j=1;j<strs.length;j++){
                // 如果首位的字符串长度已经达到当前j位的字符串的长度，则直接返回
                // 如果首位的 i 位字符不等于当前j位字符串的i列，直接返回
                if(i==strs[j].length() || strs[j].charAt(i) != c)
                    return strs[0].substring(0,i);
            }
        }
        // 全部都匹配上的情况，返回首位字符串
        return strs[0];
    }

    /**
     * 自己做出来的
     * @param strs
     * @return
     */
    public static String longestCommonPrefix1(String[] strs) {
        int n=strs.length;
        if(0==n)return "";
        StringBuilder sb = new StringBuilder();
        int j = 0;
        int cur = -1;
        boolean b = true;
        while(b){
            for(int i=0;i<n;i++){
                if(j<strs[i].length()) {
                    if(cur < 0) cur = strs[i].charAt(j);
                    if(cur == strs[i].charAt(j)){
                        continue;
                    }
                }
                return sb.toString();
            }
            j++;
            sb.append((char)cur);cur = -1;
        }
        return sb.toString();
    }

    /**
     * 分治
     * @param strs
     * @return
     */
    public static String longestCommonPrefix3(String[] strs) {
        if (strs == null || strs.length == 0) return "";
        return longestCommonPrefix(strs, 0 , strs.length - 1);
    }

    private static String longestCommonPrefix(String[] strs, int l, int r) {
        if (l == r) {
            return strs[l];
        }
        else {
            int mid = (l + r)/2;
            String lcpLeft =   longestCommonPrefix(strs, l , mid);
            String lcpRight =  longestCommonPrefix(strs, mid + 1,r);
            return commonPrefix(lcpLeft, lcpRight);
        }
    }

    static String commonPrefix(String left,String right) {
        int min = Math.min(left.length(), right.length());
        for (int i = 0; i < min; i++) {
            if ( left.charAt(i) != right.charAt(i) )
                return left.substring(0, i);
        }
        return left.substring(0, min);
    }


}
